RFC 2401—“Security Architecture for the Internet Protocol” sets forth an architecture for the implementation of security in networks that use the Internet protocol. This security architecture is commonly referred to as Ipsec. IPsec is the architecture endorsed by the Internet Engineering Task Force (IETF) for applying encryption and authentication security services to datagrams, or packets, at the IP layer of the protocol stack. The IPsec specification requires a Security Policy Database (SPD) that is used to determine how each incoming and outgoing packet is to be handled from a security perspective. The basic choices are deny packet, permit packet, and permit packet with IPsec processing. If IPsec processing is to be applied to a packet, the database specifies the precise processing that is to be applied. Because IPsec is applied at the IP layer, it is used for all upper layer protocols such as transmission control protocol (TCP), user datagram protocol (UDP), internet control message protocol (ICMP), and the like, and it is applied as a connectionless protocol. In other words, each IP packet is processed independently of any other packet.
In the known art, the SPD contains static rules and placeholders for dynamic rules. The rules and placeholders contain attributes to be matched against the corresponding attributes of incoming and outgoing packets to determine which rule should be applied to a packet. The attributes contained in the rules and placeholders might be different combinations of Internet protocol (IP) source address, source port, IP destination address, destination port, and the protocol to be used. The attributes contained within a specific rule or placeholder can be as granular as specific hosts, ports and protocol for a match to occur, or as coarse as wild carded host pairs.
A static rule is essentially a policy rule and, like most rules, contains one or more conditions and one or more actions. The conditions determine whether a packet should be governed by the rule and, if it is, the actions that are to be performed. A static rule is predefined for a network and generally is not changed very often. For example, static rules might specify that all traffic between hosts A and B will be permitted without IPsec processing and that all traffic between hosts A and C will be encrypted by IPsec. A dynamic rule is negotiated as needed and linked into the SPD database. The how, when and why of dynamic rule negotiation is not part of the present invention and is not discussed here in detail. It suffices to say that when a dynamic rule is negotiated, the placeholder that contains the most specific attributes that includes the negotiated attributes is used to link the negotiated rule into the SPD database at the appropriate point. In the known art, the static rules, dynamic rules and placeholders are searched for every incoming and outgoing packet at a node to determine how to process the packet.
The IPsec architecture also requires that the rules be defined and processed in a specific order. This requirement comes about because it is important for different hosts to apply the same type of security processing to the same packet. If a packet is encrypted with a specific algorithm, it is important that the receiving node locate the correct rule to decrypt the packet with the corresponding decryption algorithm. RFC 2401 requires that the SPD be ordered and that the SPD always be searched in the same order to insure consistent results at different nodes. The traditional technique of ordering the rules and placeholders in the SPD is from the most specific to least specific in terms of the specification of the attributes in the rules that are used for matching. Thus, the database including static, dynamic rules and placeholders is searched linearly in this order for every incoming and outgoing packet until a first match is found between the attributes of a packet and the attributes stored in a rule. At that point, the matching rule specifies whether the packet is denied, permitted without IPsec processing or permitted with IPsec processing. If the packet is permitted with IPsec processing, the database specifies the details of that processing. This processing could be authentication or encryption or both.
In systems that become aggregation points such as firewalls and servers, the number of filter rules in the database can be hundreds to thousands, depending on the network. In the known art, the SPD database is searched sequentially until a matching rule is found for all incoming and outgoing packets. This sequential search includes static rules and dynamic rules as they are encountered in the database. The performance cost on systems as a result of this searching is significant. In a system that has a mixture of IPsec and non-IPsec traffic, even the non-IPsec traffic is penalized because the filter rules must be searched to determine if a particular packet is subject to IPsec processing or not. Other typical approaches may require additional specialized hardware not typically found standard on a computer, specialized software to run on the computer running the activity monitoring software, or both.
Attwood et al. U.S. Pat. No. 6,347,376 ('376 patent) addresses methods and apparatus for searching the SPD database which involves arranging the database into a set of stable static rules and one or more sets of dynamic security rules wherein a static rule can be a placeholder for a set of dynamic rules. Rules are grouped into five groups. Each group has a different number of attributes specified. Furthermore, each group is organized in its own search tree. When an incoming packet is received, each group is searched for a match on attributes.
Callis et al. U.S. Pat. No. 6,662,235 ('235 patent) addresses methods and systems for processing a complex policy rule structured in a plurality of levels. Based on a per attribute basis, the '235 patent assigns each condition associated with an attribute to the same level. Consequently, the '235 patent assembles rules that compose a specific complex policy rule to different levels, requiring searches at different levels to fully test a complex policy rule.